//***********************************堆排序***************************************
/**
 * 堆排序是指将数组看成是完全二叉树的映射，数组下标对应二叉树的节点编号规则（层序式编号）
 * 默认升序排列（大根堆排序）
 * 基本思路是从完全二叉树的最后一个非叶子节点（对应数组下标为(arr.length-1)/2），循环调整每个子树使其成为大根堆
 * 不稳定排序，时间复杂度O(nlogn)，空间复杂度O(1)，对大文件排序比较有效
 */

function heapSort(arr) {
  // 使数组大根堆化
  turnToHeap(arr)
  // 大根堆排序
  heapSorting(arr)
}
  function turnToHeap(arr) {
    //循环调整堆，使得每一颗子树都是堆
    for(let i = Math.floor((arr.length - 1) / 2); i >= 0; i--) {
      //从最后一个非叶子节点开始调整堆
      heapAdjust(arr, i, arr.length)
    }
  }
  function heapSorting(arr) {
    //数组从后向前遍历，相当于二叉树从后逆向层序遍历
    for(let j = arr.length-1; j > 0; j--) {
      //交换最后一个值和第一个值
      //最后一个值就确定了，因为是堆顶元素赋给的，所以最大，放在最后一个
      temp = arr[j]
      arr[j] = arr[0]
      arr[0] = temp
      //调整堆，最后一项除外
      heapAdjust(arr, 0, j)
    }
  }
    function heapAdjust(arr, index, length) {
      //循环处理以当下根节点为根的子树，使其大根堆化
      for(let k = 2*index+1; k < length; k = 2*k+1) {
        let temp = arr[index]
        //比较左右节点，k指向大的节点
        if(k + 1 < length && arr[k] < arr[k+1]) {
          k++
        }
        //比较最大直接子节点和根节点的大小，子节点大就换位
        if(arr[k] > temp) {
          arr[index] = arr[k]
          //新一轮循环中index指向新根节点
          index = k
        } else {
          //如果无需交换。直接跳出循环
          break
        }
        arr[index] = temp
      }
    }

//测试用例
let arr = [19,97,01,08,09,17]
heapSort(arr)
console.log(arr);